package com.nanbei.backyracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassDescription: 回溯算法
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/15 11:28
 */
public class CombinationSumIii {
    public static void main(String[] args) {
        List<List<Integer>> lists = combinationSum3(3, 7);
        System.out.println(lists);
    }

    public static List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> coll = new ArrayList<>();
        LinkedList<Integer> stack = new LinkedList<>();
        bkSum(coll, stack, k, n,1,0);
        return coll;
    }

    // k 需要几个数字
    // n 数字相加之和
    // 之前数字的计算之和
    private static void bkSum(List<List<Integer>> coll, LinkedList<Integer> stack, int k, int n,int index,int sum) {
        if (sum == n && k == stack.size()){
            coll.add(new ArrayList<>(stack));
            return;
        }
        if (stack.size() > k || (sum < n && k == stack.size())){
            return;
        }

        for (int i = index; i <= 9; i++) {
            if (sum + i > n){
                continue;
            }
            sum += i;
            stack.push(i);
            bkSum(coll, stack, k, n, i +1,sum);
            stack.pop();
            sum -= i;
        }
    }
}
